<?php
/**
 * 实现获取最小值的栈
 * 思路就是像交换2个变量的值那样，借助另外一个栈，即用两个栈来完成获取最小值功能
 */

namespace Xxb\XxbPhpAlgo\Topic;

use Xxb\XxbPhpAlgo\ArrayStack;

class MinStack
{
    public $dataStack;
    public $minStack;

    public function __construct($capacity = 10)
    {
        $this->dataStack = new ArrayStack($capacity);
        $this->minStack = new ArrayStack($capacity);
    }

    /**
     * 入栈
     * 入最小值栈流程:
     * 1 空栈直接添加
     * 2 入栈元素和最小值比较:
     * 2.1 小于则入最小值栈
     * 2.2 大于等于 则最小值再次添加到最小值栈
     *
     * @param $ele
     */
    public function push($ele)
    {
        if ($this->dataStack->isEmpty()) {
            $this->minStack->push($ele);
        } else {
            $min = $this->minStack->top();
            if ($ele < $min) {
                $this->minStack->push($ele);
            } else {
                $this->minStack->push($min);
            }
        }
        $this->dataStack->push($ele);
    }

    /**
     * 入栈方式2，新添加元素只有小于最小值才能入最小值栈
     * 入最小值栈流程:
     * 1 空栈直接添加
     * 2 入栈元素和最小值比较，小于则入最小值栈，大于等于不入栈
     * @param $ele
     */
    public function pushOnlyMin($ele)
    {
        if ($this->dataStack->isEmpty()) {
            $this->minStack->push($ele);
        } else {
            $min = $this->minStack->top();
            if ($ele < $min) {
                $this->minStack->push($ele);
            }
        }
        $this->dataStack->push($ele);
    }

    /**
     * 出栈
     * 由于是同步入栈，所以出栈不需要比较
     */
    public function pop()
    {
        $this->dataStack->pop();
        $this->minStack->pop();
    }

    /**
     * 出栈方式2，只有删除元素等于最小值栈的栈顶，最小值栈才进行出栈操作
     * 由于最小值栈的栈顶是数据栈中所有值最小的，所以删除元素只会大于等于最小值栈的栈顶
     */
    public function popOnlyMin()
    {
        $val = $this->dataStack->top();
        $min = $this->minStack->top();

        if ($val == $min) {
            $this->minStack->pop();
        }
        $this->dataStack->pop();
    }

    /**
     * 获取栈中的最小值
     * @return mixed
     */
    public function getMin()
    {
        return $this->minStack->top();
    }
}
